package random;

/**
 * 寻找旋转排序数组中的最小值 II
 * 已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到：
 * 若旋转 4 次，则可以得到 [4,5,6,7,0,1,4]
 * 给你一个可能存在 重复 元素值的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
 */

public class L154 {

    public static void main(String[] args) {

        System.out.println(findMin(new int[]{3,1,3,3,3}));
    }

    public static int findMin(int[] nums) {

        int begin = 0;
        int end = nums.length - 1;
        if (nums.length == 1) return nums[0];
        if (nums[begin] == nums[end] && nums.length == 2) return nums[begin];
        if (nums[begin] < nums[end] ) return nums[begin];
        while (begin != end) {
            int mid = (end + begin) / 2;
            if (nums[mid] > nums[end]) {
                begin = mid;
            }else if (nums[mid] < nums[end]){
                end = mid;
            }else {
                end = end - 1;
            }
            if (begin == end - 1) {
                if (nums[begin] >= nums[end]) {
                    return nums[end];
                }else {
                    return nums[begin];
                }
            }

        }

        return 0;
    }


    /*
    官方优雅版二分法
     */
    public int findMin1(int[] nums) {
        int low = 0;
        int high = nums.length - 1;
        while (low < high) {
            int pivot = low + (high - low) / 2;
            if (nums[pivot] < nums[high]) {
                high = pivot;
            } else if (nums[pivot] > nums[high]) {
                low = pivot + 1;
            } else {
                high -= 1;
            }
        }
        return nums[low];
    }

   /* 作者：LeetCode-Solution
    链接：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/solution/xun-zhao-xuan-zhuan-pai-xu-shu-zu-zhong-de-zui--16/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。*/
}
